"""
思路找两个高峰，然后计算能存多少的水
"""

from typing import List
class Solution:
    def trap(self, height: List[int]) -> int:
        ans = current = 0
        st = []
        while current < len(height):
            while st and height[current] > height[st[-1]]:
                top = st.pop()
                if not st:
                    break
                distance = current - st[-1] - 1
                bounder_height = min(height[current], height[st[-1]]) - height[top]
                ans += distance * bounder_height
            st.append(current)
            current += 1
        return ans

def test():
    assert Solution().trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6

if __name__ == "__main__":
    
    assert Solution().trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6
    # print(Solution().trap([5,2,1,2,1,5]))
